package com.demo.java.OD1_50.OD1;

import java.util.HashMap;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 猴子爬山或上N阶台阶问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145495592
 */
public class test2 {

    // 使用 HashMap 进行记忆化，避免重复计算
    private static HashMap<Integer, Integer> memo = new HashMap<>();

    /**
     * 计算跳上台阶的方法数
     * @param step 剩余的台阶数
     * @return 可能的跳法数量
     */
    private static int getCount(int step) {
        // 如果台阶数小于3，只有一种方法（一次跳完）
        if (step < 3) {
            return 1;
        }

        // 如果已经计算过，直接返回存储的值，避免重复计算
        if (memo.containsKey(step)) {
            return memo.get(step);
        }

        // 计算当前步数的可能跳法（跳 1 步 或 跳 3 步）
        int count = getCount(step - 1) + getCount(step - 3);

        // 记忆化存储计算结果
        memo.put(step, count);

        return count;
    }

    // 主方法，用于输入台阶数并输出不同的跳法数
    public static void main(String[] args) {
        // 使用 try-with-resources 语法，确保 Scanner 资源被正确关闭
        try (Scanner scanner = new Scanner(System.in)) {
            System.out.print("请输入台阶数: ");
            if (scanner.hasNextInt()) {
                int input = scanner.nextInt();
                if (input < 0) {
                    System.out.println("台阶数不能为负数！");
                } else {
                    System.out.println("跳法总数：" + getCount(input));
                }
            } else {
                System.out.println("输入无效，请输入一个整数！");
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
